package com.lry.basic.algorithm.sort;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/25
 */
public class HeapSort {
    public static void main(String[] args) {
        int [] arr = {7,1,2,3};
        heapSort(arr);
        for (int i :arr) {
            System.out.print(i+" ");
        }
    }

    /**
     *
     * @param arr
     * @param k 当前筛的节点的小标
     * @param m 最后一个元素的小标
     */
    private static void sift(int[] arr, int k, int m){
        int i = k;//i 指向被筛选节点
        int j=2*i+1;//j 指向左右孩子较大的节点
        while(j<=m){
            if(j<m&&arr[j]<arr[j+1]){//说明右孩子较大
                ++j;
            }
            if(arr[j]<arr[i])break;
            swap(arr,i,j);
            i=j;
            j=2*i+1;
        }
    }
    public static  void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void heapSort(int[] arr) {
        //将数组调整为最大堆
        for(int i=arr.length/2-1;i>=0;i--){
            sift(arr,i,arr.length-1);
        }
        for(int i=0;i<arr.length;i++){
            //堆顶和堆尾交换
            swap(arr,0,arr.length-i-1);
            //对堆顶进行调整，这里包含了隐含的出堆
            sift(arr,0,arr.length-i-2);
        }
    }
}
